﻿// leetcode_linkedlist.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
class MyLinkedList {
public:
    MyLinkedList() {
        head = new Node(int());
        tail = head;
        size_ = 0;
    }

    int get(int index) {
        if (!checkElement(index))return -1;
        if (0 == index)
        {
            return head->next->val;
        }
        if (size_ - 1 == index)
        {
            return tail->val;
        }

        Node* curr = head->next;
        for (int i = 0; i < index; i++)
        {
            curr = curr->next;
        }
        return curr->val;
        //---get
    }

    void addAtHead(int val) {
        Node* new_node = new Node(val);
        new_node->next = head->next;
        head->next = new_node;
        if (0 == size_)
        {
            tail = new_node;
        }
        size_++;
    }

    void addAtTail(int val) {
        Node* new_node = new Node(val);
        tail->next = new_node;
        tail = new_node;
        size_++;
    }

    void addAtIndex(int index, int val) {
        if (!checkPosition(index)) return;
        if (size_ == index) {
            addAtTail(val);
            return;
        }
        if (0 == index)
        {
            addAtHead(val);
            return;
        }
        Node* prev = head;
        for (int i = 0; i < index; i++)
        {
            prev = prev->next;
        }
        Node* new_node = new Node(val);
        new_node->next = prev->next;
        prev->next = new_node;
        size_++;
    }

    void deleteFirst()
    {
        Node* first = head->next;
        head->next = first->next;
        
        if(1 == size_){
            tail = head;
        }
        delete first;
        size_--;
    }

    void deleteTail()
    {
        Node* prev = head;
        while (prev->next != tail)
        {
            prev = prev->next;
        }
        prev->next = nullptr;
        delete tail;
        tail = prev;

        size_--;
    }

    void deleteAtIndex(int index) {
        if (isEmpty())return;
        if (!checkElement(index)) return;
        if (0 == index)
        {
            deleteFirst();
            return;
        }
        if (size_ - 1 == index)
        {
            deleteTail();
            return;
        }
        Node* prev = head;
        for (int i = 0; i < index; i++)
        {
            prev = prev->next;
        }
        Node* del_node = prev->next;
        prev->next = prev->next->next;
        
        delete del_node;

        size_--;
        //---deleteAtIndex
    }

    int getSize() { return size_; }

    bool isEmpty() { return 0 == size_; }

private:
    struct Node
    {
        int val;
        Node* next;
        Node(int t) :val(t), next(nullptr) {};
    };
    Node* head;
    Node* tail;
    int size_;

    bool checkElement(int index) {
        return index >= 0 && index < size_;
    };

    bool checkPosition(int index) {
        return index >= 0 && index <= size_;
    };
};
int main()
{
    MyLinkedList* linkedlist = new MyLinkedList();
    linkedlist->addAtHead(1);
    cout << linkedlist->getSize() << endl;
    linkedlist->deleteAtIndex(1);
    
 
    
    //cout << linkedlist->getSize() << endl;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
